Batch 2 - Class 39 - Game Theory - Nim Games

• On a 4x4 chessboard, place 3 wolves and 2 sheep so that all the sheep are safe from being eaten by the wolves. 
• On a 5x5 chessboard, place 5 wolves and 3 sheep 
• Generalize! What about w wolves and s sheep on a nxn board?
• Start with 1 wolf on 3x3, 4x4, 5x5 - observe the pattern 

• Draw an alternate sorting network compared to the one discussed in class, say for selection sort or quick sort

• Describe the "Count to 20" Nim game to kids, with each player incrementing 1,2,3, or 4. Who wins the game?
• Let kids play amongst themselves for a while to discover
• What if you are counting to 21?
• What if you are allowed to increment 1, 2, 3?
• What is a general way to play this game?
• Introduce notion of winning positions if kids have not already got it
• Who will win if we are counting to 8132?
• Removing Pennies - with each kid able to remove 1,2,3 or 4 pennies
• See if kids can reason that this is same as Nim game
• What if we changed the rules so that the person to take the last penny loses?
• What is we can remove 1, 2 or 4 pennies at a time
• What if we had two piles of 7 and 10 pennies, and each player could take a match from either or both of the two piles (Person to remove the last penny wins)
• Breaking Chocolates - Start with a 6x8 chocolate. Break it along a line and eat one piece. Whoever eats the last piece wins
• Asymmetric Rook - A rook can move to left or down a 8x8 chessboard, starting at top. Player who is unable to move loses

• Number of cards -  There are nine cards on a table labeled by numbers 1 through 9. Alice and Bob take turns choosing one card. The first player who acquires three cards that total 15 wins. Find the winning strategy